WORM media have been used for years to store information in an optically-sensible form, such as by ablative recording, phasechange recording, dye recording, and the like. Most WORM media employ a single spiral track; one can treat each circumvolution of the spiral track as an addressable track; such treatment emulates the spiral track to concentric parallel tracks of a disk. The practice of the present invention is practiced with either concentric parallel tracks, with the spiral track or rectilinear tracks. It has been the practice to arrange the data on such media in linked lists of disk media addressable sectors commonly referred to as continuation chains. A directory means enables accessing any one of a multiplicity of such continuation chains. In fact, directory structures stored on such media are also stored in continuation chains. Such continuation chains are transparent to a computer user having a computer system employing such media. Commonly assigned copending application for patent Ser. No. 07/570,035, now U.S. Pat. No. 5,043,967 filed Aug. 20, 1990 shows such continuation chains.
To access the most recently recorded data in a continuation chain, it is first necessary to find the addressable area of that chain which was last recorded. Such last addressable area (sector or a cluster of sectors in an optical disk, for example)contains the most-recent data. Except for the end of a chain, no continuation chain has any null or empty addressable areas within the chain. The end of the chain is therefore indicated by a first null or empty addressable area in the chain, as further explained below.
Each of the addressable areas includes a forward pointer indicating the address of the next addressable area in the chain. In creating or extending a continuation chain, a group of addressable areas of the WORM medium are allocated to the continuation chain. Such groups of addressable areas can be of any size and can vary in size within a chain. To most easily practice the present invention, it is preferred that all groups within a chain be of a constant size, no limitation thereto intended. Each constant-sized group could occupy one track of a disk medium; of course, a group may require two or more tracks, one-half track or an arbitrary number of addressable areas or sectors. When recording data in one of the addressable areas in a continuation chain within an allocated but unfilled group of such areas, no additional allocation of addressable areas is needed; only when a current group of addressable areas is filled will an additional group of areas be allocated to a chain. From this statement, it is seen that all addressable areas in a group are contiguous on the medium while the groups may be spatially displaced.
In accessing data stored in a continuation chain, it is often desired to first access the last-recorded data, i.e. find the end of the continuation chain. The practice has been to read the entire group of addressable areas into a random access memory, then analyze the contents of the read addressable areas for finding the last-recorded area (the recorded area immediately preceding a null area is such last-recorded area). A first read failure signals a null or unrecorded but allocated area; i.e. the end of the chain. The present inventors have determined that accessing the entirety of the chain is more time-consuming than need be; therefore, a faster and more efficient linked-list endfinding method and apparatus is desired.